1. Field of the Invention
The present invention generally relates to receive circuits, for example, receive circuits which comprise two decoders separated by a deinterleave device.
Such circuits are, for example, used to decode digital video signals that can originate by radio channel from a satellite (standard DVB-S, DVB-DSNG, DirectTV, etc) or from a terrestrial base (standard DVB-T, DVB-H, ISDB, ISDB-T, ATSC, etc) or that can be conveyed by a cable (standard DVB-C, Docsis, etc).
2. Discussion of the Related Art
FIGS. 1 and 2 are diagrams respectively illustrating the elements of a transmit circuit providing a coded signal and those of a receive circuit used to decode such a coded signal.
The transmit circuit of FIG. 1 successively comprises an encoder 1, called an outer encoder, an interleave device 2, and an encoder 3, called an inner encoder. Encoder 1, for example, operates by means of a code of Reed Solomon, BCH, Hamming, etc. type. Encoder 1 receives a digital signal S to be coded and provides a signal S′ to interleave device 2. Encoder 1 generally operates by packets formed of words or multiplets, each comprising a given number of bits, 8 in the case of bytes. Interleave device 2 mixes together the multiplets of the different packets of signal S′. Encoder 3 performs a coding, for example, by means of a convolutional code, of a Turbo code, of an LDPC code, etc. Code 3 receives a signal S″ from device 2 and provides a signal S″, for example formed of symbols which are modulated to provide an electromagnetic signal. For example, a quadrature phase shift keying modulation QPSK is used. For example, to provide signals of DVB-S type, transmit circuits where encoder 1 is an encoder of Reed-Solomon type and encoder 3 is a convolutional-type encoder are currently used.
In FIG. 2, the receive circuit receives an electromagnetic signal which, after demodulation, turns into a coded signal s′″. Signal s′″ is successively processed by a decoder 10 called an inner decoder, a deinterleave device 11, and a decoder 12 called an outer decoder. Decoder 10 performs an operation inverse to that of encoder 3 and provides a signal s″ to deinterleave device 11. Deinterleave device 11 operates inversely to interleave device 2 and places the multiplets of each packet back in the order where they were before interleaving. Decoder 12 receives a signal s′ from device 11 and performs an operation inverse to that of encoder 1. Decoder 12 provides a decoded digital signal s. When encoder 3 is an encoder of convolutional type, decoder 12 generally implements a Viterbi algorithm.
FIG. 3 is an example of a digital signal S′ provided by encoder 1. In FIG. 3, each packet comprises 188 data multiplets TS, corresponding to multiplets of the digital signal S received by encoder 1, and 16 redundancy multiplets R introduced by encoder 1. The value of redundancy multiplets R is a function of the value of multiplets TS.
FIG. 4 shows a convolutional encoder 15 that may be used as an encoder 3. Encoder 15 comprises six D flip-flops 20 to 25, the output of flip-flop 20 being connected to the input of flip-flop 21, and so on. Flip-flop 20 receives signal S″. The flip-flops are controlled by a clock signal Ck so that they store the value “0” or “1” present on their input on the rising edge or the falling edge of the clock signal. Encoder 15 further comprises 8 XOR-type gates 30 to 37. Gate 30 receives signal S″ and the output of flip-flop 20. Gate 31 receives the output of gate 30 and the output of flip-flop 21. Gate 32 receives the output of gate 31 and the output of flip-flop 22. Gate 33 receives the output of gate 32 and the output of flip-flop 25. Gate 34 receives signal S″ and the output of flip-flop 21. Gate 35 receives the output of gate 34 and the output of flip-flop 22. Gate 36 receives the output of gate 35 and the output of flip-flop 24. Gate 37 receives the output of gate 36 and the output of flip-flop 25. Gate 33 outputs a digital signal X and gate 37 outputs a digital signal Y, the couples of values X and Y forming the output signal of encoder 15.
The bits of signal S″ are successively input into encoder 15 and propagate from flip-flop to flip-flop at the rate of clock signal Ck. Signals X and Y are, as for them, formed of a bit sequence output by encoder 15 at the rate of clock signal Ck.
It should be noted that each bit of signal X or Y is a combination of part of the values of 7 successive bits of signal S″, that is, the 6 values stored by flip-flops 20 to 25 and the value of the bit positioned at the input of flip-flop 20.
FIG. 5 is a diagram of a convolutional encoder 38 comprising two bits only.
In FIG. 5, flip-flops 40 and 41 are series-connected, the output of flip-flop 40 being connected to the input of flip-flop 41. Flip-flop 40 receives a data signal d. The flip-flops are controlled by a clock signal Ck. Encoder 38 further comprises three XOR gates 42, 43, and 44. Gate 42 receives signal d and the output of flip-flop 40. Gate 43 receives the output of gate 42 and the output of flip-flop 41. Gate 44 receives signal d and the output of flip-flop 41. Gates 43 and 44 provide signals also noted as X and Y.
FIG. 6 illustrates the possible state switchings of flip-flops 40 and 41. Each flip-flop can store a “1” or a “0”. The possible combinations of values stored by the pair of flip-flops 40, 41, 4 in number, are 00, 01, 10, and 11. Each possible combination is represented by a circle in which the values of the combination are written. Four circles corresponding to the couples of possible values of the flip-flops at a time n, n being an integer, are shown in a column to the left of the drawing. Similarly, four circles corresponding to the couples of possible values of the flip-flops at a time n+1 are shown in a column to the right of the drawing. The state of the flip-flops at time n is called Sn. After a clock cycle enabling switching from state Sn to a state S(n+1), flip-flop 41 stores the value previously stored by flip-flop 40 and flip-flop 40 stores the value of data signal d. A new value of data signal d further appears at the input of flip-flop 40.
Calling dn the value of signal d at time n, the values of signals X and Y at time n are defined as follows:
dnd(n−1)d(n−2)XY0000010011001111010001010110010110111110
In the case, for example, where flip-flops 40 and 41 are at state “00” at time n, signals X and Y have as values 00 or 11 respectively according to whether data signal d is equal to 0 or 1. At time n+1, flip-flops 40, 41 are at state 00 or 01 respectively according to whether signals X, Y are equal to 00 or 11 at state n. Two arrows corresponding to these two possibilities are shown in FIG. 6 between the circle corresponding to state 00 at time n shown to the left and the circles corresponding to states 00 and 10 at time n+1 shown to the right. The numbers indicated above each of the arrows correspond to the values of signals X, Y at time n.
Similarly, each other circle corresponding to a possible state Sn is connected to the two other circles corresponding to two possible states S(n+1) by arrows. Above each of the arrows are written the values of signals X, Y at time n enabling passing from state Sn corresponding to the starting circle of the arrow to state S(n+1) corresponding to the arrival circle of the arrow.
All the possibilities of state switchings of flip-flops 40 and 41 on reception of a data signal d comprising a number N of successive bits may be represented by means of a “lattice” comprising N+1 columns of four circles. Each column corresponds to a state Sn of flip-flops 40 and 41, the column corresponding to state S(n+1) being placed to the right of the column corresponding to state Sn. The leftmost column shows initial state S0 of the flip-flops before inserting the first value of data signal d into flip-flop 40. The rightmost column shows state SN of the flip-flops after insertion into flip-flop 40 of the last value of data signal d. Each circle of a column is connected to two other circles of the next column by arrows on which are written the values of signals X, Y enabling passing from one circle to the other. Further, each circle of a column is connected to two other circles of the preceding column.
A data signal d may be represented by means of such a lattice in which all the arrows except one arrow corresponding to that connecting the two states Sn and S(n+1) observed after the input of the n-th and of the (n+1)-th value of signal d in flip-flop 40 have been eliminated between each pair of columns corresponding to states Sn and S(n+1).
To restore a data signal d provided at the input of encoder 38 of FIG. 5, the decoder must find which were the successive states of flip-flops 40 and 41 based on the values of received signals X′, Y′ which, to within the transmission errors, correspond to the transmitted signals X, Y. Especially, values X′, Y′ generally do not have well-defined values 0 or 1 (called “hard” bits) but generally exhibit real values, of analog type (called soft bits). The method for searching the successive states of flip-flops 40, 41 comprises, based on a complete lattice, progressively eliminating arrows to obtain a “single” path between the lattice columns. For this purpose, the lattice is examined from left to right along the reception of signals X′, Y′ by eliminating arrows of the lattice as described schematically hereafter, in relation with FIG. 7, which illustrates the method implemented by a Viterbi decoder.
Couples p1, p2, p3, and p4 of possible values are first defined for signals X′, Y′, with for example p1=“00”, p2=“01”, p3=“10”, and p4=“11” . On reception of a new set of values of signals X′, Y′, a number c called “cost” which is all the higher as the received set of values X′, Y′ is different from the considered couple is assigned to each of couples p1 and p4. In a simple example where received values X′ and Y′ are assimilated to bits 0 or 1, if the received set of values X′, Y′ is 00, a cost c(00) equal to 0 may be assigned to couple p1 equal to 00, couples p2 and p3, which differ by one bit with respect to the received couple, receiving costs c(01) and c(10) equal to 1 and couple p4, the two bits of which are different from the received bits, receiving a cost c(11) equal to 2.
FIG. 7 comprises a series of diagrams 7-1 to 7-5 showing the progress of the elimination of the lattice arrows along the reception of signals X′, Y′.
A cumulated cost is assigned to each state shown by a circle. At the beginning of the decoding, the cumulated costs are for example all set to zero. After reception of the first set of values X′, Y′, a cost or metric is determined for each couple p1 to p4. A cumulated cost equal to the cumulated cost of the circle of origin of the arrow plus the cost associated with couple p1 to p4 corresponding to this transition is then calculated for each of the two arrows arriving on a given circle of the second column. The arrow corresponding to the highest cost is eliminated, after which the cumulated cost of the remaining arrow is assigned to the circle.
On reception of the second set of values X′, Y′, a new cost is determined for each couple p1 to p4. A cumulated cost equal to the cumulated cost of the original circle of the arrow in the second column plus the cost associated with the couple p1 to p4 corresponding to this transition is then calculated as previously for each of the two arrows arriving on a given circle of the third column. The arrow corresponding to the highest cost is eliminated, after which the cumulated cost of the remaining arrow is assigned to the circuit of the third column. Arrows which arrive on a circle from which no arrow starts back towards the next column can thus be eliminated. In the example of FIG. 7 (diagram 7-3), the arrow starting from the third circle of the first column and arriving on the fourth circle of the second column is thus eliminated.
It is thus continued for each new received set of values X′, Y′. The cumulated cost of each circle of the last column appears to be the sum of the costs of each arrow forming the single path leading to this circle. As visible on diagram 7-5, after a number of received values X′, Y′, there only remains a single arrow between the first and second columns and between the second and third columns. The first three states S0, S1, and S2 of the flip-flops can then be noted and the first two values of signal d which is desired to be restored can be deduced therefrom. In the example of FIG. 7, S0=01, S1=10, and S2=01, the flip-flops were thus initially positioned at 01, after which the values of signal d have successively been 1, then 0.
FIG. 8 is a diagram of a portion of a decoder 48 enabling implementing the above-described decoding method. Decoder 48 comprises four blocks b1, b2, b3, and b4 of identical structures. The j-th block, with j ranging between 1 and 4, comprises two adders 50j and 51j having their outputs connected to a comparator 52j and to two inputs of a multiplexer 53j. The output of multiplexer 53j is connected to a register or accumulator 54j. Multiplexer 53j is controlled by comparator 52j.
Registers 541 to 544 are respectively called R00, R01, R10, R11. Each register R00 to R11 is used to store the cumulated metric associated with each circle of the n-th column after reception of the n-th set of values X′, Y′. Thus, register R00 is associated with the circle corresponding to state Sn=00 and so on.
Further, costs c(00), c(01), c(10), and c(11) associated with couples p1 to p4 are provided on lines also called c(00), c(01), c(10), and c(11).
In the case of first block b1, the inputs of adder 501 are connected to register R00 and to line c(00). The inputs of adder 511 are connected to register R01 and to line c(11). It should be noted that these connections to adders 501 and 511 can be deduced from the diagram of FIG. 6. Thus, referring to FIG. 6, it is possible to deduce the connections to the adders of the other decoder blocks.
The operation of decoder 48 is the following. When an n-th set of values X′, Y′ is received, the lines of costs c(00) to c(11) are updated. Each j-th block then performs the following operations. Adders 50j, 51j are activated and each provide a sum value. Comparator 52j then determines which is the lowest sum and controls multiplexer 53j so that the lowest sum is stored in register 54j. This comparison and storage operation corresponds to the elimination of one of the two arrows arriving on the circle associated with register 54j and to the calculation of the cumulated metric associated with this circle.
Further, comparator 52j of each block j is connected to a memory called a “survivor memory” which enables determining the most probable path followed by the transitions between states, for example, by storing the remaining arrows after each add/compare/store cycle performed after arrival of a new set of values X′, Y′.
The decoder described hereabove in relation with FIG. 8 uses a Viterbi algorithm and enables decoding of data coded by a convolutional encoder with two flip-flops. A Viterbi decoder corresponding to a convolutional encoder comprising more flip-flops, such as that of FIG. 4, may easily be designed according to the above-described principle.
Referring to FIG. 2, decoder 12 analyzes each packet of multiplets coming from deinterleave device 11 and determines, based on the redundancy multiplets, whether or not there are erroneous multiplets in the packet. If the number of erroneous multiplets is not too high, the latter are corrected. The decoder then eliminates the redundancy multiplets and transmits a corrected signal s only formed of the data multiplets.
The decoding and/or reception circuits described hereabove enable eliminating a number of errors introduced into the signals on transmission thereof between the transmit circuit and the receive circuit.
However, when the transmission media are significantly noisy, the number of corrected errors is insufficient. Such is for example the case when the transmissions are performed by radio channel, especially from a satellite.